﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;

namespace Brain.Logic2D.PathFinding.Tiled
{
    public enum PathFinderStatus
    {
        Stopped, Searching, Finished, NoPath
    }
    public class PathFinder
    {
        /// <summary>
        /// The 2D Map of blocks
        /// </summary>
        public Map Map;

        /// <summary>
        /// The current Path Finder Status
        /// </summary>
        public PathFinderStatus Status
        {
            get;
            protected set;
        }

        /// <summary>
        /// Open List with Blocks being analyzed by the Finder.
        /// </summary>
        public List<PathNodeInfo> OpenList;

        /// <summary>
        /// The List with the Way
        /// </summary>
        public List<Node> WayList;

        internal List<Node> UsedList;

        /// <summary>
        /// If it should look for Diagonal blocks. Not recommended,
        /// because In 2D, Diagonal ways can be a little strange, 
        /// and it will hurt perfomance(doubles the time)
        /// </summary>
        public bool UseDiagonal = false;

        /// <summary>
        /// If the Path Finder should find the way in only 1
        /// Update call(it will use a While and will not stop
        /// until it find the path). Not recommended, this
        /// can slow down your game if the way is too big
        /// </summary>
        public bool CalculateAllAtOnce = false;

        /// <summary>
        /// If CalculateAllAtOnce is false, then this will be the TimeStep
        /// it will take to update again
        /// </summary>
        public int TimeStep = 32;

        /// <summary>
        /// How much Operations it should do in 1 update call
        /// </summary>
        public int OperationsPerUpdate = 1;

        /// <summary>
        /// If it should use Indexing to find near nodes. If false, Needs a Map.FinishedMaking, if you made the Map without a Texture.
        /// </summary>
        public bool UseIndexing = false;

        public PathFinder(Map Map)
        {
            this.Map = Map;
            OpenList = new List<PathNodeInfo>();
            UsedList = new List<Node>();

            WayList = new List<Node>();
        }

        /// <summary>
        /// The Start Node(where it begun)
        /// </summary>
        public Node Start { get; protected set; }
        /// <summary>
        /// The End Node(where it will end)
        /// </summary>
        public Node End { get; protected set; }

        /// <summary>
        /// Start searching for a way
        /// </summary>
        /// <param name="start"></param>
        /// <param name="end"></param>
        public virtual void Search(Node start, Node end)
        {
            this.WayList.Clear();
            this.WayList.Capacity = 0;
            this.OpenList.Clear();
            this.OpenList.Capacity = 0;
            this.UsedList.Clear();
            this.UsedList.Capacity = 0;

            this.Start = start;
            this.End = end;
            this.Status = PathFinderStatus.Searching;
        }

        public event SetVoid FoundPath;

        internal PathNodeInfo LastNode;

        internal int timer = 0;
        public virtual void Update()
        {
            if (CalculateAllAtOnce)
            {
                while (this.Status == PathFinderStatus.Searching)
                {
                    Search();
                }
            }
            else
            {
                timer += Engine.Instance.GameTime.ElapsedGameTime.Milliseconds;
                if (timer > this.TimeStep)
                {
                    timer = 0;
                    if (this.Status == PathFinderStatus.Searching)
                    {
                        int op = OperationsPerUpdate;
                        while (op > 0)
                        {
                            Search();
                            op--;
                        }
                    }
                }
            }
        }
        protected virtual void Search()
        {
            // Primeiro, procuramos em todas as direcoes se há algum bloco adjacente
            FindNode(1, 0);
            FindNode(-1, 0);
            FindNode(0, 1);
            FindNode(0, -1);
            if (UseDiagonal)
            {
                FindNode(1, 1);
                FindNode(-1, 1);
                FindNode(1, -1);
                FindNode(-1, -1);
            }

            int Minimum = int.MaxValue;
            int Index = -1;
            PathNodeInfo Node = null;
            for (int i = 0; i < OpenList.Count; i++)
            {
                PathNodeInfo node = OpenList[i];
                if (node.F < Minimum)
                {
                    Minimum = node.F;
                    Index = i;
                    Node = node;
                }
            }
            if (Index != -1)
            {
                LastNode = Node;
                OpenList.RemoveAt(Index);
            }
            else
            {
                Status = PathFinderStatus.NoPath;
            }
        }

        protected virtual void FindNode(int X, int Y)
        {
            Node node = null;
            int nX = X;
            int nY = Y;
            if (UseIndexing)
            {
                if (LastNode == null)
                {
                    nX = Start.X;
                    nY = Start.Y;
                }
                else
                {
                    nX += LastNode.Parent.X;
                    nY += LastNode.Parent.Y;
                }
                if (nX >= 0 && nX < Map.Width &&
                    nY >= 0 && nY < Map.Height)
                {
                    node = Map.Nodes[nX, nY];
                }
            }
            else
            {
                Node toSearch = null;
                if (LastNode == null)
                {
                    int finalX = Start.X;
                    finalX = finalX > 0 ? finalX : 0;
                    int finalY = Start.Y;
                    finalY = finalY > 0 ? finalY : 0;
                    toSearch = Map.Nodes[finalX, finalY];
                }
                else
                {
                    toSearch = LastNode.Parent;
                }
                if (X == 1 && Y == 0)
                {
                    node = toSearch.RightNode;
                }
                else if (X == -1 && Y == 0)
                {
                    node = toSearch.LeftNode;
                }
                else if (X == 0 && Y == 1)
                {
                    node = toSearch.UpNode;
                }
                else if (X == 0 && Y == -1)
                {
                    node = toSearch.DownNode;
                }
            }
            if (node == null)
            {
                return;
            }
            // Last case, check if we already used that Node
            if (this.UsedList.Contains(node))
            {
                return;
            }

            if (node == End)
            {
                Status = PathFinderStatus.Finished;

                FindParentAndWay(LastNode);

                if (FoundPath != null)
                {
                    FoundPath();
                }
            }

            UsedList.Add(node);

            // Inside the Map
            if (node.Blocked)
            {
                return;
            }
            else
            {
                PathNodeInfo info = new PathNodeInfo(node);
                info.InfoParent = LastNode;
                // Manhattan
                // F = G + H
                // F -> soma de G + H
                // G -> valor gasto do ponto de partida para o quadrado
                // H -> valor gasto do quadrado ao final
                int sX = Start.X;
                int sY = Start.Y;

                int nX_sX = node.X - sX;
                int nY_sY = node.Y - sY;
                int G = nX_sX + nY_sY;

                int eX = End.X;
                int eY = End.Y;
                int nX_eX = node.X - eX;
                int nY_eY = node.Y - eY;
                int H = nX_eX + nY_eY;

                info.F = H + G;

                OpenList.Add(info);

                return;
            }

            return;
        }
        /*protected virtual void FindNode(int X, int Y, PathNodeInfo parent)
        {
            int nX = X;
            int nY = Y;
            if (LastNode == null)
            {
                nX += Start.X;
                nY += Start.Y;
            }
            else
            {
                nX += LastNode.Parent.X;
                nY += LastNode.Parent.Y;
            }

            if (nX >= Map.Width ||
                nY >= Map.Height)
            {
                // Out of the Map
                return;
            }
            else
            {
                if (nX >= 0 &&
                    nY >= 0)
                {
                    Node node = Map.Nodes[nX, nY];
                    // Last case, check if we already used that Node
                    if (this.UsedList.Contains(node))
                    {
                        return;
                    }

                    if (node == End)
                    {
                        Status = PathFinderStatus.Finished;

                        FindParentAndWay(LastNode);
                    }

                    UsedList.Add(node);

                    // Inside the Map
                    if (node.Blocked)
                    {
                        return;
                    }
                    else
                    {
                        PathNodeInfo info = new PathNodeInfo(node);
                        info.InfoParent = LastNode;
                        // Manhattan
                        // F = G + H
                        // F -> soma de G + H
                        // G -> valor gasto do ponto de partida para o quadrado
                        // H -> valor gasto do quadrado ao final
                        int sX = Start.X;
                        int sY = Start.Y;

                        int nX_sX = nX - sX;
                        int nY_sY = nY - sY;
                        int G = nX_sX + nY_sY;
                        info.G = G;

                        int eX = End.X;
                        int eY = End.Y;
                        int nX_eX = nX - eX;
                        int nY_eY = nY - eY;
                        int H = nX_eX + nY_eY;
                        info.H = H;

                        OpenList.Add(info);

                        return;
                    }
                }
            }
            return;
        }*/

        protected virtual void FindParentAndWay(PathNodeInfo info)
        {
            if (info != null)
            {
                WayList.Add(info.Parent);
                FindParentAndWay(info.InfoParent);
            }
        }
    }
}
